package com.ctrip.demo.leetcode;

import java.util.Arrays;

public class LeetCode2049 {

    static int N = 100010, M = N * 2;

    static int[] he = new int[N],  e = new int[M], ne = new int[M];
    static int[] f = new int[N];

    int idx;
    void add(int a, int b) {
        e[idx] = b;
        ne[idx] = he[a];
        he[a] = idx ++;
    }

    public static void main(String[] args) {
        System.out.println(Double.parseDouble("11.2"));
        System.out.println(new LeetCode2049().countHighestScoreNodes(new int[]{-1, 2, 0, 2, 0}));
    }

    public int countHighestScoreNodes(int[] parents) {
        Arrays.fill(he, -1);
        int n = parents.length;
        for (int i = 1; i < n; i++) {
            add(parents[i], i);
        }
        dfs(0);
        long max = 0;
        int res = 0;
        for (int i = 0; i < n; i++) {
            long cur = 1;
            for (int j = he[i]; j != -1; j = ne[j]) {
                cur *= f[e[i]];
            }
            if (i != 0) {
                cur *= n - f[i];
            }
            if (cur > max) {
                max = cur;
                res = 1;
            } else if (cur == max) {
                res ++;
            }
        }
        return res;
    }

    int dfs(int u) {
        int ans = 1;
        for (int i = he[u]; i != -1; i= ne[i]) {
            ans += dfs(e[i]);
        }
        f[u] = ans;
        return ans;
    }
}
